1. Field of the Invention
This invention relates generally to a system for authentication between two parties--for example, a user and a host computer. More particularly, the present invention relates to a system for generating challenges and responses, based on a function generated from specific input values, between an authenticating party and a party to be authenticated in order to establish the identities of either or both.
2. Description of the Related Art
One method for protecting valuable computer based resources and digital services, such as computer time sharing services, computer information services (e.g., CompuServe.RTM. Information Service), automated teller machines, pay television, etc., is to employ an authentication mechanism that controls access to the computer or service (the host). Authentication protects resources by stopping vandals before they enter the host. Today, most authentication methods require a computer or service user (the user) to prove his or her identity before accessing the host. Therefore, authentication takes place during an initial login sequence. If the user is unable to prove his or her identity during this sequence, access to the host will be denied. While authentication may be enforced only during an initial login sequence, it may also be enforced throughout an entire session so that the host and/or user identities are authenticated with each transmission or after some number of transmissions during the session.
During any authentication sequence, security may be breached in several ways. First, the user may not be the person he or she purports to be and is in reality, a computer vandal (an opponent). Second, the host may not be the entity it purports to be so that the user logs into an imposter host which can then gain valuable personal information (e.g., credit card numbers). Finally, an eavesdropper may be monitoring the exchange between the user and the host in order to capture information that may be used to breach security during this or a subsequent session. Given the possible security breaches that may occur during an authentication sequence, there is a need for individuals who use various computer based services or other digital services to be able to identify themselves to the host in a way that makes impersonation by anyone else difficult, and preferably, impossible. In some applications, authentication may be carried out continuously throughout the session.
Most login sequences begin with the host prompting the user for an identification name or number and a password (sometimes called a personal identification number or PIN). This approach involves a two stage process in which the user and host first agree on a user ID, such as an authentication name or number, and an associated password. This is done in a secure manner--for example, in a personal meeting or via mail. Both the host and the user store these values. When the user desires service, he sends his user ID and password to the host. The host then compares the offered password with the value previously stored by the host for that user. If the offered and stored passwords agree, the user is granted access to services. If they disagree, the user is prompted to try again because users make occasional typing errors. However, the rate at which passwords may be tried is often limited (e.g., once every five seconds) to prevent automated attacks in which passwords are tried at electronic speeds--potentially thousands of passwords per second. For similar reasons, the number of incorrect login attempts is often limited (e.g., to three) before the user account is put on hold pending investigation of a possible attack. These limits place little or no burden on legitimate users because humans can only enter a password once every few seconds and rarely enter incorrect passwords many times in a row. However, these limits may thwart the efforts of an opponent using an automated attack because the attack is at least interrupted if not stopped completely.
Security under this mechanism may be breached when the user ID and password are told to, guessed, or captured by an opponent. One method for capturing passwords is to eavesdrop on channels carrying passwords. "Password login" security has sufficed for many services that rely on the dial-up telephone network because eavesdropping on a telephone call carried over the dial-up network requires a wiretap--an invasive act susceptible to detection and apprehension of the wiretapper. However, "password login" is highly insecure when used on new, shared communication channels such as local area networks (LANs), the Internet, cellular telephones, etc. Eavesdropping on shared communication channels is accomplished easily, with little chance of detection, because of their shared nature. For example, on a LAN, each user's computer sees all messages going to any other computer, but a legitimate user's network adapter (e.g., an Ethernet card) is programmed to only pick off and store those messages with that user's address. It is a simple matter, almost impossible to detect, for the user to reprogram the network adapter to store all messages with one or more other users' addresses. Debugging tools in some network adapters facilitate eavesdropping under so-called "promiscuous listening mode." This mode is intended for network administrators' trouble shooting, but may be used by dishonest users as well.
Challenge-response schemes attempt to address the eavesdropping problem. When the host computer answers the user's authentication request, it initiates a dialog by sending the user a challenge which either never repeats--for example, the date and time--or has negligible probability of repeating--for example a 64-bit random value. The user's computer receives the host's challenge, encrypts it under a password supplied by the user, and returns the response to the host. The host also knows this password and can authenticate the user's identity by comparing this user's response with a correctly encrypted version of the challenge. Because the password itself is never sent, an eavesdropper must cryptanalyze the system in order to impersonate a user.
Variations of this challenge and response authentication include requiring the user to send a challenge to the host so that the host authenticates itself to the user, thereby preventing an opponent from posing as the host. Under this scheme, the user sends a challenge to the host, the host generates the response to the challenge as above, and the user checks the validity of the host's response. Authentication of the host may be important if the user is communicating confidential information.
Bi-directional or mutual authentication, in which both host and user authenticate each other, is also clearly possible. Under this two-way scheme, the user must prove his or her identity to the host and the host must prove its identity to the user. In some instances (e.g., if the challenge is the date and time), the challenge may be generated by the user or a third party, rather than by the host. In the former case, the challenge need not be transmitted to the user. A similar option exists in bidirectional authentication.
While such challenge-response schemes provide a defense against eavesdroppers, short passwords are insecure because an eavesdropping opponent can search through all possiblities rapidly. In particular, short passwords are often susceptible to "dictionary attacks" in which an opponent attempts to guess the password by monitoring the challenges and responses and testing frequently used passwords (e.g., the user's name) by performing the same operations as the user and host computers. Dictionary attacks may be thwarted by requiring longer passwords, perhaps as long as cryptographic keys. For example, if the Data Encryption Standard (DES) is used as the cryptographic system in the challenge and response authentication, and if the password is a 56-bit totally random value (the size of DES's key), then an opponent must search 2.sup.56 =7E16 values. If the password is four alphanumeric characters, instead, the opponent must search only 36.sup.4 =2E6 values. If the opponent can search 1E5 values per second (a typical value for a modem PC), searching for the totally random key takes 7E11 seconds=20,000 years, but, searching for a four character alphanumeric key takes only 20 seconds.
If the password must be memorized or entered manually by the user, there is great user resistance to using long, random passwords. Even when passwords are stored in script files that are communicated automatically to the host, many users select passwords that are short or non-random.